package com.lwt.codetop.arrayOrSort;
// 54. 螺旋矩阵

import java.util.ArrayList;
import java.util.List;

/**
 * 思路：模拟，遇到边界时改变方向，为此我们要进行方向的控制和改变
 */
public class SpiralMatrix {
    public static void main(String[] args) {
        // 构建测试用例
        int[][] g = new int[][] {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        // 模拟遍历
        List<Integer> res = spiralOrder(g);
        System.out.println(res);
    }

    /**
     * 模拟遍历
     * @param g
     * @return
     */
    private static List<Integer> spiralOrder(int[][] g) {
        List<Integer> res = new ArrayList<>();
        int n = g.length, m = g[0].length;
        boolean[][] st = new boolean[n + 10][m + 10];
        // 定义方向
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int d = 0; // 用于方向控制
        int k = 0;
        int x = 0, y = 0;
        while(k < n * m){
            st[x][y] = true;
            res.add(g[x][y]);
            int a = x + dx[d], b = y + dy[d];// 这里用d一直控制方向
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
                d = (d + 1) % 4;
                a = x + dx[d];
                b = y + dy[d];
            }
            // 更新位置移动
            x = a;
            y = b;
            k += 1;
        }
        return res;
    }
}
